package com.xzz.stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author: hhz
 * @create: 2021-12-29 15:02
 * 739. 每日温度
 * 请根据每日 气温 列表 temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 **/
public class DailyTemperatures {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{89,62,70,58,47,47,46,76,100,70})));
    }
    public static int[] dailyTemperatures(int[] temperatures) {
        //存索引
        int[] res = new int[temperatures.length];
        //倒着入栈
        Stack<Integer> stack = new Stack<>();
        for (int i = temperatures.length-1; i >=0; i--) {
            while (!stack.empty() && temperatures[stack.peek()]<=temperatures[i]){
                stack.pop();
            }
            res[i]=stack.empty()?0:(stack.peek()-i);
            stack.push(i);
        }
        return res;
    }
}
